import org.springframework.util.CollectionUtils;

import java.util.*;

public class YouZhuDemo {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

    }
    public ArrayList<ArrayList<Integer>> threeSum (int[] nums) {
        // write code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int val = nums[i];
            HashMap<Integer,Integer> hashMap = new HashMap<>();
            for (int j = i+1; j < nums.length; j++) {
                if(hashMap.containsValue(0-(val+nums[j]))) {
                    ArrayList<Integer> second = new ArrayList<>();
                    second.add(val);
                    second.add(nums[j]);
                    second.add(0 - (val + nums[j]));
                    Collections.sort(second);
                    if (!result.contains(second)) result.add(second);
                }else{
                    hashMap.put(j,nums[j]);
                }
            }
        }
        Collections.sort(result, (ArrayList<Integer> o1, ArrayList<Integer> o2)-> {
                for (int i = 0; i < o1.size()&&i<o2.size(); i++) {
                    if(o1.get(i)>o2.get(i)){
                        return 1;
                    }else if(o1.get(i)<o2.get(i)){
                        return -1;
                    }
                }
                return 0;
        });
        return result;
    }
    public int minPathSum (int[][] grid) {
        // write code here
        if(grid == null || grid.length==0 || grid[0].length==0){
            return 0;
        }
        int hang = grid.length,lie = grid[0].length;
        int [][]dp = new int[hang][lie];
        dp[0][0] = grid[0][0];
        for (int i = 0; i < hang; i++) {
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for (int i = 0; i < lie; i++) {
            dp[0][i] = dp[0][i-1] + grid[0][i];
        }
        for (int i = 1; i < hang; i++) {
            for (int j = 1; j < lie; j++) {
                dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
            }
        }
        return dp[hang-1][lie-1];
    }
    public int Trap (ArrayList<Integer> height) {
        // write code here
        int l = 0,r = height.size()-1;
        int result = 0;
        if(height.size()==0) return 0;
        int maxL = 0 ,maxR = 0;
        while (l<r){
            maxL = Math.max(maxL,height.get(l));
            maxR = Math.max(maxR,height.get(r));
            if(height.get(l)<height.get(r)){
                result += maxL-height.get(l);
                l=l+1;
            }else{
                result += maxR - height.get(r);
                r = r-1;
            }
        }
        return result;
    }

}
